//
//  AVLTree.hpp
//  AVLTree
//
//  Created by Shane on 17/9/28.
//  Copyright © 2017年 Shane. All rights reserved.
//

#ifndef AVLTree_hpp
#define AVLTree_hpp

#include "AVLTreeNode.hpp"
#include <algorithm>
using namespace std;

template <class T>
class AVLTree {
public:
    AVLTree(){
        
    }
    ~AVLTree(){
        
    }
public:
    int height();
private:
    int height(AVLTreeNode<T> *root);
    
    //LL: 左左对应的情况(左单旋转)
    AVLTreeNode<T>* leftLeftRotation(AVLTreeNode<T> *k2);
    
    //RR: 右右对应的情况(右单旋转)
    AVLTreeNode<T>* rightRightRotation(AVLTreeNode<T> *k1);
    
    //LR: 左右对应的情况(左双旋转)
    AVLTreeNode<T>* leftRightRotation(AVLTreeNode<T> *k3);
    
    //RL: 右左对应的情况(右双旋转)
    AVLTreeNode<T>* rightLeftRotation(AVLTreeNode<T> *k1);
private:
    AVLTreeNode<T> *m_root;
    
};


template <class T>
int AVLTree<T>::height(){
    return height(m_root);
}

template <class T>
int AVLTree<T>::height(AVLTreeNode<T> *root){
    if (!root) {
        return root->height;
    }
    return 0;
}


template <class T>
AVLTreeNode<T>* AVLTree<T>::leftLeftRotation(AVLTreeNode<T> *k2){
    AVLTreeNode<T> *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    
    k2->height = max(height(k2->left), height(k2->right)) + 1;
    k1->height = max(height(k1->left), k2->height) + 1;
    
    return k1;
}

template <class T>
AVLTreeNode<T>* AVLTree<T>::rightRightRotation(AVLTreeNode<T> *k1) {
    AVLTreeNode<T>* k2;
    
    k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    
    k1->height = max( height(k1->left), height(k1->right)) + 1;
    k2->height = max( height(k2->right), k1->height) + 1;
    
    return k2;
}




#endif /* AVLTree_hpp */
